#include "linearList.h"
#include<iostream>
#include<algorithm>
#include<cstdlib>
#include<malloc.h>
using namespace std;
sequenceList::sequenceList(const int& a, const int& b, float c[])
{
    maxCapcity = a;
    myList = (float*)malloc(sizeof(float) * a);
    if (!myList)exit(1);
    curNumberOfItem = b;
    for (int s = 0; s < b; s++)
    {
        myList[s] = c[s];
    }
}
sequenceList::~sequenceList()
{
    maxCapcity = 0;
    curNumberOfItem = 0;
    free(myList);
    myList = nullptr;
}
bool sequenceList::addItem(const float& a)
{
    if (myList == NULL || curNumberOfItem >= maxCapcity)return false;
    curNumberOfItem++;
    myList[curNumberOfItem - 1] = a;
    return true;
}
bool sequenceList::insertItem(const int& a, const float& b)
{
    if (curNumberOfItem >= maxCapcity)return false;
    if (a < 0 || a >= maxCapcity)return false;
    curNumberOfItem++;
    for (int i = curNumberOfItem - 1; i > a; i--)  myList[i] = myList[i - 1];
    myList[a] = b;
    return true;
}
int sequenceList::deleteItem(const float& a)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == a)
        {
            for (int j = i; j < curNumberOfItem - 1; j++)myList[j] = myList[j + 1];
            curNumberOfItem--;//遗漏了一次改变长度
            return i + 1;
        }
    }
    return -1;
}
bool sequenceList::locate(const int& a, float& b)
{
    if (!curNumberOfItem)return false;
    if (a < 0 || a >= maxCapcity)return false;
    b = myList[a];
    return true;
}
int sequenceList::locate(const float& a)
{
    for (int i = 0; i < curNumberOfItem; i++)
    {
        if (myList[i] == a)return i;
    }
    return -1;
}
void sequenceList::reverse()
{

    for (int i = 0, j = curNumberOfItem - 1; i <= j; i++, j--)
    {
        float s = myList[j];
        myList[j] = myList[i];
        myList[i] = s;
    }
}
//顺序表打印
void sequenceList::print()
{
    cout << curNumberOfItem << ":";

    for (int i = 0; i < curNumberOfItem - 1; i++)
    {
        cout << myList[i] << ",";
    }

    cout << myList[curNumberOfItem - 1] << endl;
}


linkList::linkList(const int& a, float b[])
{
    listSize = a;
    firstNode = (listNode*)malloc(sizeof(listNode));
    if (!firstNode)exit(1);
    firstNode->next = (listNode*)malloc(sizeof(listNode));
    if (!firstNode->next)exit(1);
    listNode* head = firstNode->next;
    for (int i = 0; i < a - 1; i++)
    {
        head->data = b[i];
        head->next = (listNode*)malloc(sizeof(listNode));
        if (!head->next)exit(1);
        head = head->next;
    }
    head->data = b[a - 1];
    lastNode = head;
    lastNode->next = nullptr;
}
linkList::~linkList()
{

}
bool linkList::headInsertItem(const float& a)
{
    listSize++;
    listNode* p = (listNode*)malloc(sizeof(listNode));
    if (!p)exit(1);
    p->data = a;
    p->next = firstNode->next;
    firstNode->next = p;
    return true;
}
bool linkList::tailInsertItem(const float& a)
{
    listSize++;
    listNode* p = (listNode*)malloc(sizeof(listNode));
    if (!p)exit(1);
    p->data = a;
    lastNode->next = p;
    lastNode = p;
    return true;
}
int linkList::insertItem(const int& a, const float& b)
{
    if (a > -1 && a < listSize)
    {
        curNode = firstNode;
        for (int i = 0; i <= a - 1; i++)
        {
            curNode = curNode->next;
        }
        listNode* target = (listNode*)malloc(sizeof(listNode));
        if (!target)exit(1);
        target->data = b;
        target->next = curNode->next;
        curNode->next = target;
        listSize++;
        return a;
    }
    return -1;
}
int linkList::deleteItem(const float& num)
{
    int ans = 0;
    curNode = firstNode->next;
    while (curNode->data == num)
    {
        listSize--;
        firstNode->next = curNode->next;
        curNode = firstNode->next;
        ans = 0;
        return ans;
    }
    listNode* beforep = curNode;
    curNode = curNode->next;
    for (int i = 1; i < listSize - 1; i++, beforep = curNode, curNode = curNode->next)
    {
        while (curNode->data == num)
        {
            listSize--;
            beforep->next = curNode->next;
            curNode = curNode->next;
            ans = i;
            return ans;
        }
    }
    while (lastNode->data == num)
    {
        curNode->next = NULL; return listSize - 1;
    }
    return -1;
}
bool linkList::locate(const int& location, float& val)
{

    if (location > -1 && location < listSize)
    {
        curNode = firstNode->next;
        for (int i = 1; i <= location; i++)
        {
            curNode = curNode->next;
        }
        val = curNode->data;
        return true;
    }
    return false;
}
int linkList::locate(const float& num)//按值查找
{
    curNode = firstNode->next;
    int i = 0;
    while (curNode != NULL&&curNode->data != num)
    {
        i++;
        curNode = curNode->next;
    }
    if (curNode == NULL)return -1;
    return i;

}
void linkList::ascendingOrder()
{
    for (int i = 0; i < listSize; i++)
    {
        listNode* target = firstNode->next;
        for (int j = 0; j < listSize - i - 1; j++, target = target->next)
        {
            if (target->data - target->next->data > 1e-8)//
            {
                float cmp = target->data;
                target->data = target->next->data;
                target->next->data = cmp;
            }

        }
    }
}
void linkList::reverse()
{
    listNode* ahead = firstNode->next;
    listNode* targetnow = ahead;
    listNode* before = nullptr;
    for (int i = 0; i < listSize; i++)
    {
        ahead = targetnow->next;
        targetnow->next = before;
        before = targetnow;
        targetnow = ahead;
    }
    lastNode = firstNode->next;
    firstNode->next = before;
}

//链表打印
void linkList::print()
{
    curNode = firstNode;

    cout << listSize << ":";

    while (curNode != lastNode)
    {
        if (curNode->next == lastNode)
            cout << curNode->next->data << endl;
        else
        {
            cout << curNode->next->data << ",";
        }


        curNode = curNode->next;
    }
}
void merge(linkList& a, linkList& b)
{

    a.lastNode->next = b.firstNode->next;
    a.lastNode = b.lastNode;
    a.lastNode->next = nullptr;
    a.listSize = a.listSize + b.listSize;
    a.ascendingOrder();
    a.reverse();
    return;
}